package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * @author tzp
 * @since 2020/9/22
 */
public class LC664_1 implements DynamicProblem {
    int[][] memo;

    public int strangePrinter(String s) {
        if (s == null || s.length() == 0) return 0;
        s = compress(s);
        int N = s.length();
        memo = new int[N][N];
        return dp(s, 0, N - 1);
    }

    public int dp(String s, int i, int j) {
        if (i > j) return 0;
        if (memo[i][j] == 0) {
            int ans = dp(s, i + 1, j) + 1;
            for (int k = i + 1; k <= j; ++k)
                if (s.charAt(k) == s.charAt(i))
                    ans = Math.min(ans, dp(s, i, k - 1) + dp(s, k + 1, j));
            memo[i][j] = ans;
        }
        return memo[i][j];
    }

    public static String compress(String s) {
        StringBuilder sb = new StringBuilder();
        sb.append(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != sb.charAt(sb.length() - 1)) {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}
